<!DOCTYPE HTML>
<html lang="zh-CN">


<head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="utf-8">
    <meta name="keywords" content="贪心算法, Cloud Nactive  MachineLearning 卫占军 机器学习">
    <meta name="description" content="贪心算法‍
算法综述贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
算法定义贪心的本质是选择每一阶段的局部最优，从而达到全局最优。难点就是如何通过局部最优，推出整体最优。

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，指">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="referrer" content="no-referrer-when-downgrade">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>贪心算法 | 个人博客</title>
    <link rel="icon" type="image/png" href="https://resource.weizhanjun.com/public/medias/favicon.png">
    


    <!-- bg-cover style     -->



<link rel="stylesheet" type="text/css" href="../../../../../../libs/awesome/css/all.min.css">
<link rel="stylesheet" type="text/css" href="../../../../../../libs/materialize/materialize.min.css">
<link rel="stylesheet" type="text/css" href="../../../../../../libs/aos/aos.css">
<link rel="stylesheet" type="text/css" href="../../../../../../libs/animate/animate.min.css">
<link rel="stylesheet" type="text/css" href="../../../../../../libs/lightGallery/css/lightgallery.min.css">
<link rel="stylesheet" type="text/css" href="../../../../../../css/matery.css">
<link rel="stylesheet" type="text/css" href="../../../../../../css/my.css">
<link rel="stylesheet" type="text/css" href="../../../../../../css/dark.css" media="none" onload="if(media!='all')media='all'">




    <link rel="stylesheet" href="../../../../../../libs/tocbot/tocbot.css">
    <link rel="stylesheet" href="../../../../../../css/post.css">




    



    <script src="../../../../../../libs/jquery/jquery-3.6.0.min.js"></script>

<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"></head>


<body>
    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="../../../../../../index.html" class="waves-effect waves-light">
                    
                    <img src="https://resource.weizhanjun.com/public/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">个人博客</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="../../../../../../index.html" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>首页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="../../../../../../tags" class="waves-effect waves-light">
      
      <i class="fas fa-tags" style="zoom: 0.6;"></i>
      
      <span>标签</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="../../../../../../categories" class="waves-effect waves-light">
      
      <i class="fas fa-bookmark" style="zoom: 0.6;"></i>
      
      <span>分类</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="../../../../../../archives" class="waves-effect waves-light">
      
      <i class="fas fa-archive" style="zoom: 0.6;"></i>
      
      <span>归档</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="../../../../../../about" class="waves-effect waves-light">
      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于</span>
    </a>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="搜索" style="zoom: 0.85;"></i>
    </a>
  </li>
  <li>
    <a href="javascript:;" class="waves-effect waves-light" onclick="switchNightMode()" title="深色/浅色模式" >
      <i id="sum-moon-icon" class="fas fa-sun" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>


<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="https://resource.weizhanjun.com/public/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">个人博客</div>
        <div class="logo-desc">
            
            云架构 | MLOps | 机器学习
            
        </div>
    </div>

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="../../../../../../index.html" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			首页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="../../../../../../tags" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-tags"></i>
			
			标签
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="../../../../../../categories" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-bookmark"></i>
			
			分类
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="../../../../../../archives" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-archive"></i>
			
			归档
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="../../../../../../about" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-user-circle"></i>
			
			关于
		</a>
          
        </li>
        
        
    </ul>
</div>


        </div>

        
    </nav>

</header>

    
<script src="../../../../../../libs/cryptojs/crypto-js.min.js"></script>
<script>
    (function() {
        let pwd = '';
        if (pwd && pwd.length > 0) {
            if (pwd !== CryptoJS.SHA256(prompt('dream')).toString(CryptoJS.enc.Hex)) {
                alert('密码错误，将返回主页！');
                location.href = '../../../../../../index.html';
            }
        }
    })();
</script>




<div class="bg-cover pd-header post-cover" style="background-image: url('https://resource.weizhanjun.com/public/medias/featureimages/6.jpg')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">贪心算法</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="../../../../../../tags/LeetCode/">
                                <span class="chip bg-color">LeetCode</span>
                            </a>
                        
                            <a href="../../../../../../tags/贪心算法/">
                                <span class="chip bg-color">贪心算法</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2023-01-20
                </div>
                

                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-check fa-fw"></i>更新日期:&nbsp;&nbsp;
                    2023-01-20
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-file-word fa-fw"></i>文章字数:&nbsp;&nbsp;
                    6.8k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-clock fa-fw"></i>阅读时长:&nbsp;&nbsp;
                    28 分
                </div>
                

                
                    <div id="busuanzi_container_page_pv" class="info-break-policy">
                        <i class="far fa-eye fa-fw"></i>阅读次数:&nbsp;&nbsp;
                        <span id="busuanzi_value_page_pv"></span>
                    </div>
				
            </div>
        </div>
        <hr class="clearfix">

        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <h1 id="贪心算法"><a href="#贪心算法" class="headerlink" title="贪心算法"></a>贪心算法</h1><p>‍</p>
<h1 id="算法综述"><a href="#算法综述" class="headerlink" title="算法综述"></a>算法综述</h1><p>贪心的本质是选择每一阶段的局部最优，从而达到全局最优。</p>
<h2 id="算法定义"><a href="#算法定义" class="headerlink" title="算法定义"></a>算法定义</h2><p>贪心的本质是选择每一阶段的局部最优，从而达到全局最优。难点就是如何通过局部最优，推出整体最优。</p>
<blockquote>
<p>例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，指定每次拿最大的，最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。</p>
</blockquote>
<h2 id="算法模版"><a href="#算法模版" class="headerlink" title="算法模版"></a>算法模版</h2><blockquote>
<p>贪心算法的难点就是如何通过局部最优，推出整体最优。这往往没有固定的策略，靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。</p>
<p>最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。</p>
</blockquote>
<p>贪心算法一般分为如下四步：</p>
<ol>
<li>将问题分解为若干个子问题</li>
<li>找出适合的贪心策略</li>
<li>求解每一个子问题的最优解</li>
<li>将局部最优解堆叠成全局最优解</li>
</ol>
<h2 id="算法应用场景"><a href="#算法应用场景" class="headerlink" title="算法应用场景"></a>算法应用场景</h2><p>‍</p>
<p>‍</p>
<h1 id="刷题路线"><a href="#刷题路线" class="headerlink" title="刷题路线"></a>刷题路线</h1><p>​<img src="https://resource.weizhanjun.com/public/images/20230110211226.png" alt="">​</p>
<h1 id="刷题记录"><a href="#刷题记录" class="headerlink" title="刷题记录"></a>刷题记录</h1><h2 id="简单难度"><a href="#简单难度" class="headerlink" title="简单难度"></a>简单难度</h2><h3 id="问题-分发饼干"><a href="#问题-分发饼干" class="headerlink" title="问题: 分发饼干"></a>问题: 分发饼干</h3><p><a href="https://leetcode.cn/problems/assign-cookies/">LeetCode</a></p>
<blockquote>
<p>假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。</p>
<p>对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] &gt;= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。</p>
</blockquote>
<p>‍</p>
<h4 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<p>这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。</p>
<p>先将饼干数组和小孩数组排序, 然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。</p>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230110203853.png" alt="">​</p>
</blockquote>
<p>‍</p>
<h4 id="Go题解"><a href="#Go题解" class="headerlink" title="Go题解"></a>Go题解</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">findContentChildren</span><span class="token punctuation">(</span>g <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> s <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 小孩和饼干数组排序</span>
    sort<span class="token punctuation">.</span><span class="token function">Ints</span><span class="token punctuation">(</span>g<span class="token punctuation">)</span>
    sort<span class="token punctuation">.</span><span class="token function">Ints</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span>
    <span class="token comment" spellcheck="true">// 定义饼干数组小标</span>
    index <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span>
    <span class="token comment" spellcheck="true">// 倒序遍历小孩数组</span>
    result <span class="token operator">:=</span> <span class="token number">0</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token function">len</span><span class="token punctuation">(</span>g<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span> <span class="token punctuation">{</span>
        <span class="token comment" spellcheck="true">// 饼干没有分完，且当前小孩胃口小于饼干尺寸, 饼干分出去</span>
        <span class="token keyword">if</span> index <span class="token operator">>=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> g<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;=</span> s<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token punctuation">{</span>
            result<span class="token operator">++</span>
            index<span class="token operator">--</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result 
<span class="token punctuation">}</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解"><a href="#C-题解" class="headerlink" title="C++题解"></a>C++题解</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">findContentChildren</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> g<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> s<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">sort</span><span class="token punctuation">(</span>g<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> g<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">sort</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> s<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> index <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>g<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">>=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> g<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;=</span> s<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                result<span class="token operator">++</span><span class="token punctuation">;</span>
                index<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>‍</p>
<h4 id="Python题解"><a href="#Python题解" class="headerlink" title="Python题解"></a>Python题解</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">findContentChildren</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> g<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">,</span> s<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> int<span class="token punctuation">:</span>
        g<span class="token punctuation">.</span>sort<span class="token punctuation">(</span><span class="token punctuation">)</span>
        s<span class="token punctuation">.</span>sort<span class="token punctuation">(</span><span class="token punctuation">)</span>
        res <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span>len<span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            <span class="token comment" spellcheck="true"># 小孩轮流来领饼干，当饼干满足胃口就分出去</span>
            <span class="token keyword">if</span> res <span class="token operator">&lt;</span> len<span class="token punctuation">(</span>g<span class="token punctuation">)</span> <span class="token operator">and</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">>=</span> g<span class="token punctuation">[</span>res<span class="token punctuation">]</span><span class="token punctuation">:</span>
                res <span class="token operator">+=</span> <span class="token number">1</span>
        <span class="token keyword">return</span> res<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="算法优化"><a href="#算法优化" class="headerlink" title="算法优化"></a>算法优化</h4><blockquote>
<p>文中详细介绍了思考的过程，想清楚局部最优，想清楚全局最优，感觉局部最优是可以推出全局最优，并想不出反例，那么就试一试贪心。</p>
</blockquote>
<p>‍</p>
<h3 id="问题：1005K次取反后最大化的数组和"><a href="#问题：1005K次取反后最大化的数组和" class="headerlink" title="问题：1005K次取反后最大化的数组和"></a>问题：1005K次取反后最大化的数组和</h3><p><a href="https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/">LeetCode</a></p>
<blockquote>
<p>给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：</p>
<p>选择某个下标 i 并将 nums[i] 替换为 -nums[i]</p>
<p>重复这个过程恰好 k 次。可以多次选择同一个下标 i</p>
<p>以这种方式修改数组后，返回数组 可能的最大和 。</p>
<p>提示：</p>
<p>1 &lt;= nums.length &lt;= 104<br>-100 &lt;= nums[i] &lt;= 100<br>1 &lt;= k &lt;= 104</p>
<p>示例1:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>示例2:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>示例3:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
</blockquote>
<p>‍</p>
<h4 id="解题思路-1"><a href="#解题思路-1" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<p>贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。</p>
<p>那么本题的解题步骤为：</p>
<p>第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小<br>第二步：从前向后遍历，遇到负数将其变为正数，同时K–<br>第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完<br>第四步：求和</p>
</blockquote>
<h4 id="Go-题解"><a href="#Go-题解" class="headerlink" title="Go 题解"></a>Go 题解</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">largestSumAfterKNegations</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> k <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    sort<span class="token punctuation">.</span><span class="token function">Slice</span><span class="token punctuation">(</span>nums<span class="token punctuation">,</span> <span class="token keyword">func</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> j <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> math<span class="token punctuation">.</span><span class="token function">Abs</span><span class="token punctuation">(</span><span class="token function">float64</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">></span> math<span class="token punctuation">.</span><span class="token function">Abs</span><span class="token punctuation">(</span><span class="token function">float64</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span><span class="token punctuation">)</span>

    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> k <span class="token operator">></span><span class="token number">0</span> <span class="token punctuation">{</span>
            nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">*=</span> <span class="token operator">-</span><span class="token number">1</span>
            k<span class="token operator">--</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> k <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> k <span class="token operator">%</span> <span class="token number">2</span> <span class="token operator">==</span><span class="token number">1</span> <span class="token punctuation">{</span>
        nums<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*=</span> <span class="token operator">-</span><span class="token number">1</span>
    <span class="token punctuation">}</span>
    result <span class="token operator">:=</span> <span class="token number">0</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        result <span class="token operator">+=</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result
<span class="token punctuation">}</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解-1"><a href="#C-题解-1" class="headerlink" title="C++ 题解"></a>C++ 题解</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
<span class="token keyword">static</span> bool <span class="token function">cmp</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">abs</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span> <span class="token operator">></span> <span class="token function">abs</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">largestSumAfterKNegations</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> nums<span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">sort</span><span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> nums<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> cmp<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> k <span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                k<span class="token operator">--</span><span class="token punctuation">;</span>
                nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">*</span><span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>k <span class="token operator">></span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> k <span class="token operator">%</span> <span class="token number">2</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            nums<span class="token punctuation">[</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> n <span class="token punctuation">:</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            result <span class="token operator">+</span><span class="token operator">=</span> n<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Python-题解"><a href="#Python-题解" class="headerlink" title="Python 题解"></a>Python 题解</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">largestSumAfterKNegations</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> nums<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">,</span> k<span class="token punctuation">:</span> int<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> int<span class="token punctuation">:</span>
        nums <span class="token operator">=</span> sorted<span class="token punctuation">(</span>nums<span class="token punctuation">,</span> key<span class="token operator">=</span>abs<span class="token punctuation">,</span> reverse<span class="token operator">=</span><span class="token boolean">True</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span>len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;</span><span class="token number">0</span> <span class="token operator">and</span> k <span class="token operator">></span><span class="token number">0</span><span class="token punctuation">:</span>
                nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">*=</span> <span class="token operator">-</span><span class="token number">1</span>
                k <span class="token operator">-=</span> <span class="token number">1</span>
        <span class="token keyword">if</span> k <span class="token operator">></span><span class="token number">0</span> <span class="token operator">and</span> k <span class="token operator">%</span> <span class="token number">2</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">:</span>
            nums<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*=</span> <span class="token operator">-</span><span class="token number">1</span>
        <span class="token keyword">return</span> sum<span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="算法优化总结"><a href="#算法优化总结" class="headerlink" title="算法优化总结"></a>算法优化总结</h4><blockquote>
<p>‍</p>
</blockquote>
<p>‍</p>
<p>‍</p>
<p>‍</p>
<p>‍</p>
<h2 id="中等难度"><a href="#中等难度" class="headerlink" title="中等难度"></a>中等难度</h2><h3 id="问题：摆动序列"><a href="#问题：摆动序列" class="headerlink" title="问题：摆动序列"></a>问题：摆动序列</h3><p><a href="https://leetcode.cn/problems/wiggle-subsequence/">LeetCode</a></p>
<blockquote>
<p>如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。</p>
<ul>
<li>例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。</li>
<li>相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。</li>
</ul>
<p>子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。</p>
<p>给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。</p>
</blockquote>
<p>‍</p>
<h4 id="解题思路-2"><a href="#解题思路-2" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230110222257.png" alt="">​</p>
<p>局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。</p>
<p>整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。</p>
<p>在计算是否有峰值的时候，遍历下标i ，计算prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff &lt; 0 &amp;&amp; curdiff &gt; 0 或者 prediff &gt; 0 &amp;&amp; curdiff &lt; 0 此时就有波动就需要统计。</p>
<p>但本题要考虑三种情况：</p>
<p><strong>情况一</strong>：上下坡中有平坡</p>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230110222700.png" alt=""></p>
<p>长度是3，也就是我们在删除的时候 要不删除左面的三个2，要不就删除右边的三个2。</p>
<p>在图中，当i指向第一个2的时候，prediff &gt; 0 &amp;&amp; curdiff = 0 ，当 i 指向最后一个2的时候 prediff = 0 &amp;&amp; curdiff &lt; 0。</p>
<p>删左面三个2的规则，那么 当 prediff = 0 &amp;&amp; curdiff &lt; 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。</p>
<p>所以我们记录峰值的条件应该是： (preDiff &lt;= 0 &amp;&amp; curDiff &gt; 0) || (preDiff &gt;= 0 &amp;&amp; curDiff &lt; 0)，为什么这里允许 prediff == 0 ，就是为了 上面我说的这种情况。</p>
<p><strong>情况二</strong>：数组首尾两端</p>
<p>题目中说了，如果只有两个不同的元素，那摆动序列也是2。例如序列[2,5]，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。因为我们在计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。可以单独判断元素为2时的条件，如果只有两个元素，且元素不同，那么结果为2。</p>
<p><strong>情况三</strong>：单调坡中有平坡</p>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230110223428.png" alt="">​</p>
<p>‍</p>
<p>‍</p>
</blockquote>
<h4 id="Go-题解-1"><a href="#Go-题解-1" class="headerlink" title="Go 题解"></a>Go 题解</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">wiggleMaxLength</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">&lt;=</span> <span class="token number">1</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span> nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> nums<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">1</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">2</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    curDiff <span class="token operator">:=</span> <span class="token number">0</span>
    preDiff <span class="token operator">:=</span> <span class="token number">0</span>
    result <span class="token operator">:=</span> <span class="token number">1</span>

    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token punctuation">{</span>
        curDiff <span class="token operator">=</span> nums<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">-</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>preDiff <span class="token operator">&lt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> curDiff<span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token punctuation">(</span>preDiff <span class="token operator">>=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> curDiff<span class="token operator">&lt;</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            result<span class="token operator">++</span>
            preDiff <span class="token operator">=</span> curDiff
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解-2"><a href="#C-题解-2" class="headerlink" title="C++ 题解"></a>C++ 题解</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">wiggleMaxLength</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&lt;=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> nums<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> <span class="token number">2</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">int</span> curDiff <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> preDiff <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> result  <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            curDiff <span class="token operator">=</span> nums<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">-</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>preDiff <span class="token operator">&lt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> curDiff <span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token punctuation">(</span>preDiff <span class="token operator">>=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> curDiff <span class="token operator">&lt;</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                result<span class="token operator">++</span><span class="token punctuation">;</span>
                preDiff <span class="token operator">=</span> curDiff<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Python-题解-1"><a href="#Python-题解-1" class="headerlink" title="Python 题解"></a>Python 题解</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">wiggleMaxLength</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> nums<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> int<span class="token punctuation">:</span>
        preDiff<span class="token punctuation">,</span> curDiff<span class="token punctuation">,</span> result <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span>
        <span class="token keyword">if</span> len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">&lt;=</span> <span class="token number">1</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span>
        <span class="token keyword">if</span> len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> nums<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">:</span>
                <span class="token keyword">return</span> <span class="token number">1</span>
            <span class="token keyword">else</span><span class="token punctuation">:</span>
                <span class="token keyword">return</span> <span class="token number">2</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span>len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            curDiff <span class="token operator">=</span> nums<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">-</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token keyword">if</span> curDiff <span class="token operator">*</span> preDiff <span class="token operator">&lt;=</span><span class="token number">0</span> <span class="token operator">and</span> curDiff<span class="token operator">!=</span><span class="token number">0</span><span class="token punctuation">:</span> <span class="token comment" spellcheck="true"># curDiff * preDiff 为负，表示有摆动</span>
                result <span class="token operator">+=</span><span class="token number">1</span>
                preDiff <span class="token operator">=</span> curDiff

        <span class="token keyword">return</span> result<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="优化总结"><a href="#优化总结" class="headerlink" title="优化总结"></a>优化总结</h4><ul>
<li><input disabled="" type="checkbox"> 动态规划解题</li>
</ul>
<p>‍</p>
<h3 id="问题：122-买卖股票的最佳时机II"><a href="#问题：122-买卖股票的最佳时机II" class="headerlink" title="问题：122.买卖股票的最佳时机II"></a>问题：122.买卖股票的最佳时机II</h3><p><a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/">LeetCode</a></p>
<blockquote>
<p>给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的 最大 利润 。</p>
<p>提示：</p>
<p>1 &lt;= prices.length &lt;= 3 * 104<br>0 &lt;= prices[i] &lt;= 104</p>
<p>示例1:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>示例2:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>
<p>示例3:</p>
<pre class="line-numbers language-shell"><code class="language-shell"><span aria-hidden="true" class="line-numbers-rows"><span></span></span></code></pre>
<p>‍</p>
<p>弟弟</p>
</blockquote>
<h4 id="解题思路-3"><a href="#解题思路-3" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<p>这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…..循环反复。如果想到其实最终利润是可以分解的，那么本题就很容易了！</p>
<p>假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。</p>
<p>此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1])…..(prices[1] - prices[0])。</p>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230112142600.png" alt="">​</p>
<p>局部最优：收集每天的正利润，全局最优：求得最大利润。时间复杂度：O(n), 空间复杂度：O(1)</p>
<ul>
<li><input disabled="" type="checkbox"> 动态规划解法</li>
</ul>
<p>‍</p>
</blockquote>
<h4 id="Go-题解-2"><a href="#Go-题解-2" class="headerlink" title="Go 题解"></a>Go 题解</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">maxProfit</span><span class="token punctuation">(</span>prices <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>prices<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token number">0</span>
    <span class="token punctuation">}</span>
    res <span class="token operator">:=</span> <span class="token number">0</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>prices<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> prices<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>prices<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span><span class="token number">0</span> <span class="token punctuation">{</span>
            res <span class="token operator">+=</span> prices<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>prices<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> res
<span class="token punctuation">}</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解-3"><a href="#C-题解-3" class="headerlink" title="C++ 题解"></a>C++ 题解</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">maxProfit</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> prices<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>prices<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>prices<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>prices<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">-</span> prices<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                result <span class="token operator">+</span><span class="token operator">=</span> prices<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">-</span> prices<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Python-题解-2"><a href="#Python-题解-2" class="headerlink" title="Python 题解"></a>Python 题解</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">maxProfit</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> prices<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> int<span class="token punctuation">:</span>
        <span class="token keyword">if</span> len<span class="token punctuation">(</span>prices<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token number">0</span>
        result <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span>len<span class="token punctuation">(</span>prices<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> prices<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>prices<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span><span class="token number">0</span><span class="token punctuation">:</span>
                result <span class="token operator">+=</span> prices<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>prices<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token keyword">return</span> result<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="算法优化总结-1"><a href="#算法优化总结-1" class="headerlink" title="算法优化总结"></a>算法优化总结</h4><blockquote>
<p>股票问题其实是一个系列的，属于动态规划的范畴，但是使用贪心往往比动态规划更巧妙，更好用。</p>
<p>本题中理解利润拆分是关键点！ 不要整块的去看，而是把整体利润拆为每天的利润。</p>
</blockquote>
<p>‍</p>
<h3 id="问题：134-加油站"><a href="#问题：134-加油站" class="headerlink" title="问题：134.加油站"></a>问题：134.加油站</h3><p><a href="https://leetcode.cn/problems/gas-station/">LeetCode</a></p>
<blockquote>
<p>在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。</p>
<p>提示:</p>
<p>gas.length == n<br>cost.length == n<br>1 &lt;= n &lt;= 105<br>0 &lt;= gas[i], cost[i] &lt;= 104</p>
<p>示例1:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>示例2:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</blockquote>
<h4 id="解题思路-4"><a href="#解题思路-4" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<h5 id="暴力破解"><a href="#暴力破解" class="headerlink" title="暴力破解"></a>暴力破解</h5><p>暴力的方法很明显就是$O(n^2)$的，遍历每一个加油站为起点的情况，模拟一圈。如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。</p>
<p>for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！</p>
<p>时间复杂度：O(n^2)，空间复杂度：O(1)</p>
<h5 id="贪心算法1"><a href="#贪心算法1" class="headerlink" title="贪心算法1"></a>贪心算法1</h5><p>直接从全局进行贪心选择，情况如下：</p>
<p>情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的</p>
<p>情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。</p>
<p>情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。</p>
<h5 id="贪心2"><a href="#贪心2" class="headerlink" title="贪心2"></a>贪心2</h5><p>首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。</p>
<p>每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。</p>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230112220909.png" alt="">​</p>
<p>为什么一旦[i，j] 区间和为负数，起始位置就可以是j+1呢，j+1后面就不会出现更大的负数？如果出现更大的负数，就是更新j，那么起始位置又变成新的j+1了。</p>
<p>而且j之前出现了多少负数，j后面就会出现多少正数，因为耗油总和是大于零的(以可以跑完全程为前提)</p>
<p>那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。</p>
</blockquote>
<h4 id="Go-题解（暴力破解）"><a href="#Go-题解（暴力破解）" class="headerlink" title="Go 题解（暴力破解）"></a>Go 题解（暴力破解）</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">canCompleteCircuit</span><span class="token punctuation">(</span>gas <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> cost <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 遍历加油站</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>cost<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token comment" spellcheck="true">// 油箱剩余量</span>
        rest <span class="token operator">:=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        index <span class="token operator">:=</span> <span class="token punctuation">(</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token function">len</span><span class="token punctuation">(</span>cost<span class="token punctuation">)</span>
        <span class="token comment" spellcheck="true">// go没有while，使用for代替</span>
        <span class="token keyword">for</span> <span class="token punctuation">{</span>
            <span class="token comment" spellcheck="true">// 油耗尽或者回到出发点加油站，退出</span>
            <span class="token keyword">if</span> rest <span class="token operator">&lt;=</span><span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">==</span> i <span class="token punctuation">{</span>
                <span class="token keyword">break</span>
            <span class="token punctuation">}</span>
            rest <span class="token operator">+=</span> gas<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token operator">-</span> cost<span class="token punctuation">[</span>index<span class="token punctuation">]</span>
            index <span class="token operator">=</span> <span class="token punctuation">(</span>index <span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token function">len</span><span class="token punctuation">(</span>cost<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">if</span> rest <span class="token operator">>=</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> index <span class="token operator">==</span> i <span class="token punctuation">{</span>
            <span class="token keyword">return</span> i
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
<span class="token punctuation">}</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Go-题解（贪心2）"><a href="#Go-题解（贪心2）" class="headerlink" title="Go 题解（贪心2）"></a>Go 题解（贪心2）</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">canCompleteCircuit</span><span class="token punctuation">(</span>gas <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> cost <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    curSum <span class="token operator">:=</span> <span class="token number">0</span>
    totalSum <span class="token operator">:=</span> <span class="token number">0</span>
    index <span class="token operator">:=</span> <span class="token number">0</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>gas<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        curSum <span class="token operator">+=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span>cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        totalSum <span class="token operator">+=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span>cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token keyword">if</span> curSum <span class="token operator">&lt;</span><span class="token number">0</span> <span class="token punctuation">{</span>
            index <span class="token operator">=</span> i<span class="token operator">+</span><span class="token number">1</span>
            curSum <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> totalSum <span class="token operator">&lt;</span><span class="token number">0</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> index
<span class="token punctuation">}</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解（暴力破解）"><a href="#C-题解（暴力破解）" class="headerlink" title="C++ 题解（暴力破解）"></a>C++ 题解（暴力破解）</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">canCompleteCircuit</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> gas<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> cost<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>cost<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> rest <span class="token operator">=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">int</span> index <span class="token operator">=</span> <span class="token punctuation">(</span>i <span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> cost<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">while</span> <span class="token punctuation">(</span>rest <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> index <span class="token operator">!=</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                rest <span class="token operator">+</span><span class="token operator">=</span> gas<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token operator">-</span> cost<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span>
                index <span class="token operator">=</span> <span class="token punctuation">(</span>index<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> cost<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>rest <span class="token operator">>=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> index <span class="token operator">==</span> i<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> i<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解（贪心1）"><a href="#C-题解（贪心1）" class="headerlink" title="C++ 题解（贪心1）"></a>C++ 题解（贪心1）</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">canCompleteCircuit</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> gas<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> cost<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> curSum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> min <span class="token operator">=</span> INT_MAX<span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 从起点出发，油箱里的油量最小值</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>gas<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> rest <span class="token operator">=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span>cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            curSum <span class="token operator">+</span><span class="token operator">=</span> rest<span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>curSum <span class="token operator">&lt;</span> min<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                min <span class="token operator">=</span> curSum<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>curSum <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 情况一</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>min <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 情况二</span>

        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> gas<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> rest <span class="token operator">=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            min <span class="token operator">+</span><span class="token operator">=</span> rest<span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>min <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> i<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Python-题解（贪心2）"><a href="#Python-题解（贪心2）" class="headerlink" title="Python 题解（贪心2）"></a>Python 题解（贪心2）</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">canCompleteCircuit</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> gas<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">,</span> cost<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> int<span class="token punctuation">:</span>
        totalSum<span class="token punctuation">,</span> curSum<span class="token punctuation">,</span> index <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span>len<span class="token punctuation">(</span>gas<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            curSum <span class="token operator">+=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            totalSum <span class="token operator">+=</span> gas<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> cost<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token keyword">if</span> curSum <span class="token operator">&lt;</span><span class="token number">0</span><span class="token punctuation">:</span>
                index <span class="token operator">=</span> i<span class="token operator">+</span><span class="token number">1</span>
                curSum <span class="token operator">=</span> <span class="token number">0</span>    

        <span class="token keyword">if</span> totalSum <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
        <span class="token keyword">return</span> index <span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="算法优化总结-2"><a href="#算法优化总结-2" class="headerlink" title="算法优化总结"></a>算法优化总结</h4><blockquote>
<p>‍</p>
</blockquote>
<p>‍</p>
<p>‍</p>
<p>‍</p>
<p>‍</p>
<p>‍</p>
<hr>
<h2 id="困难难度"><a href="#困难难度" class="headerlink" title="困难难度"></a>困难难度</h2><h3 id="问题：最大子序和"><a href="#问题：最大子序和" class="headerlink" title="问题：最大子序和"></a>问题：最大子序和</h3><p><a href="https://leetcode.cn/problems/maximum-subarray/">LeetCode</a></p>
<blockquote>
<p>给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。</p>
<p>提示：</p>
<p>1 &lt;= nums.length &lt;= 105<br>-104 &lt;= nums[i] &lt;= 104</p>
<p><strong>示例1:</strong></p>
<pre class="line-numbers language-plaintext"><code class="language-plaintext">输入：nums = [1]
输出：1<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
<p><strong>示例2:</strong></p>
<pre class="line-numbers language-plaintext"><code class="language-plaintext">输入：nums = [5,4,-1,7,8]
输出：23<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
</blockquote>
<h4 id="解题思路-5"><a href="#解题思路-5" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<h5 id="暴力解法"><a href="#暴力解法" class="headerlink" title="暴力解法"></a>暴力解法</h5><p>第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值，时间复杂度O(n^2)，空间复杂度：O(1)</p>
<pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">maxSubArray</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> result <span class="token operator">=</span> INT32_MIN<span class="token punctuation">;</span>
        <span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment" spellcheck="true">// 设置起始位置</span>
            count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i<span class="token punctuation">;</span> j <span class="token operator">&lt;</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment" spellcheck="true">// 每次从起始位置i开始遍历寻找最大值</span>
                count <span class="token operator">+</span><span class="token operator">=</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                result <span class="token operator">=</span> count <span class="token operator">></span> result <span class="token operator">?</span> count <span class="token punctuation">:</span> result<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>C++勉强可以过，其他语言运行超时。</p>
<h5 id="贪心解法"><a href="#贪心解法" class="headerlink" title="贪心解法"></a>贪心解法</h5><p><strong>局部最优</strong>：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。</p>
<p><strong>全局最优</strong>：选取最大“连续和”</p>
<p>局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。</p>
<p>遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。</p>
<p>这相当于是暴力解法中的不断调整最大子序和区间的起始位置。</p>
<p>区间的终止位置，其实就是如果count取到最大值了，及时记录下来了。代码看C++题解，<strong>时间复杂度：O(n)，空间复杂度：O(1)</strong></p>
<ul>
<li><input disabled="" type="checkbox"> 动态规划解法</li>
</ul>
</blockquote>
<p>‍</p>
<h4 id="Go-题解-3"><a href="#Go-题解-3" class="headerlink" title="Go 题解"></a>Go 题解</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">maxSubArray</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    result <span class="token operator">:=</span> <span class="token operator">^</span><span class="token function">int</span><span class="token punctuation">(</span><span class="token operator">^</span><span class="token function">uint</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">>></span><span class="token number">1</span><span class="token punctuation">)</span>
    count <span class="token operator">:=</span> <span class="token number">0</span>

    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        count <span class="token operator">=</span> count <span class="token operator">+</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token comment" spellcheck="true">// 取区间累计的最大值（相当于不断确定最大子序终止位置）</span>
        <span class="token keyword">if</span> count <span class="token operator">></span> result <span class="token punctuation">{</span>
            result <span class="token operator">=</span> count
        <span class="token punctuation">}</span>
        <span class="token keyword">if</span> count <span class="token operator">&lt;=</span> <span class="token number">0</span> <span class="token punctuation">{</span>
            <span class="token comment" spellcheck="true">// 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和</span>
            count <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解-4"><a href="#C-题解-4" class="headerlink" title="C++ 题解"></a>C++ 题解</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">maxSubArray</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> result <span class="token operator">=</span> INT32_MIN<span class="token punctuation">;</span>
        <span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            count <span class="token operator">+</span><span class="token operator">=</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>count <span class="token operator">></span> result<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                result <span class="token operator">=</span> count<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>count <span class="token operator">&lt;=</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Python-题解-3"><a href="#Python-题解-3" class="headerlink" title="Python 题解"></a>Python 题解</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">maxSubArray</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> nums<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> int<span class="token punctuation">:</span>
        result <span class="token operator">=</span> <span class="token operator">-</span>float<span class="token punctuation">(</span><span class="token string">'inf'</span><span class="token punctuation">)</span>
        count <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span>len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            count <span class="token operator">+=</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token keyword">if</span> count <span class="token operator">></span> result<span class="token punctuation">:</span>
                result <span class="token operator">=</span> count
            <span class="token keyword">if</span> count <span class="token operator">&lt;=</span> <span class="token number">0</span><span class="token punctuation">:</span>
                count <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token keyword">return</span> result<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="算法优化总结-3"><a href="#算法优化总结-3" class="headerlink" title="算法优化总结"></a>算法优化总结</h4><blockquote>
<p>贪心没套路，就刷题而言，如果感觉好像局部最优可以推出全局最优，然后想不到反例，那就试一试贪心吧！</p>
<p>贪心的思路为局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优：选取最大“连续和”</p>
</blockquote>
<p>‍</p>
<h3 id="问题：跳跃游戏"><a href="#问题：跳跃游戏" class="headerlink" title="问题：跳跃游戏"></a>问题：跳跃游戏</h3><p><a href="https://leetcode.cn/problems/jump-game/">LeetCode</a></p>
<blockquote>
<p>给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。</p>
<p>数组中的每个元素代表你在该位置可以跳跃的最大长度。</p>
<p>判断你是否能够到达最后一个下标。</p>
<p>提示：</p>
<p>1 &lt;= nums.length &lt;= 3 * 104<br>0 &lt;= nums[i] &lt;= 105</p>
<p>示例1:</p>
<p>输入：nums = [2,3,1,1,4]<br>输出：true<br>解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。</p>
<p>示例2:</p>
<p>输入：nums = [3,2,1,0,4]<br>输出：false<br>解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。</p>
<p>‍</p>
</blockquote>
<h4 id="解题思路-6"><a href="#解题思路-6" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<p>看到题目，当前位置元素如果是3，第一时间想到究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？其实跳几步无所谓，关键在于可跳的覆盖范围！</p>
<p>不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。那么<strong>这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点</strong>！</p>
<p>贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。</p>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230111204342.png" alt="">​</p>
<p>i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。</p>
<p>而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。</p>
<p>如果cover大于等于了终点下标，直接return true就可以了。</p>
</blockquote>
<h4 id="Go-题解-4"><a href="#Go-题解-4" class="headerlink" title="Go 题解"></a>Go 题解</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">canJump</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 数组长度为1，直接访问true</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token boolean">true</span>
    <span class="token punctuation">}</span>
    <span class="token comment" spellcheck="true">// 初始化跳跃范围为0</span>
    cover <span class="token operator">:=</span> <span class="token number">0</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>cover<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        cover <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>i<span class="token operator">+</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> cover<span class="token punctuation">)</span>
        <span class="token keyword">if</span> cover <span class="token operator">>=</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token boolean">true</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token boolean">false</span>
<span class="token punctuation">}</span>

<span class="token keyword">func</span> <span class="token function">max</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> y <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> x<span class="token operator">-</span>y <span class="token operator">>=</span><span class="token number">0</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> x
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> y
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解-5"><a href="#C-题解-5" class="headerlink" title="C++ 题解"></a>C++ 题解</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    bool <span class="token function">canJump</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> cover <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> true<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;=</span>cover<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            cover <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>i <span class="token operator">+</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> cover<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>cover <span class="token operator">>=</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> true<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> false<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Python-题解-4"><a href="#Python-题解-4" class="headerlink" title="Python 题解"></a>Python 题解</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">canJump</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> nums<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> bool<span class="token punctuation">:</span>
        <span class="token keyword">if</span> len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token boolean">True</span>
        cover <span class="token operator">=</span> <span class="token number">0</span>
        i <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token keyword">while</span> i <span class="token operator">&lt;=</span> cover<span class="token punctuation">:</span>
            cover <span class="token operator">=</span> max<span class="token punctuation">(</span>i<span class="token operator">+</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> cover<span class="token punctuation">)</span>
            <span class="token keyword">if</span> cover <span class="token operator">>=</span> len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">:</span>
                <span class="token keyword">return</span> <span class="token boolean">True</span>
            i <span class="token operator">+=</span> <span class="token number">1</span>
        <span class="token keyword">return</span> <span class="token boolean">False</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="优化总结-1"><a href="#优化总结-1" class="headerlink" title="优化总结"></a>优化总结</h4><p>这道题目关键点在于：不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。</p>
<p>这道题和贪心算法看似没有关系？</p>
<p><strong>是真的就是没什么联系，因为贪心无套路！</strong>没有个整体的贪心框架解决一系列问题，只能是接触各种类型的题目锻炼自己的贪心思维！</p>
<p>‍</p>
<h3 id="问题：45-跳跃游戏II"><a href="#问题：45-跳跃游戏II" class="headerlink" title="问题：45.跳跃游戏II"></a>问题：45.跳跃游戏II</h3><p><a href="https://leetcode.cn/problems/jump-game-ii/">LeetCode</a></p>
<blockquote>
<p>给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:</p>
<p>0 &lt;= j &lt;= nums[i]<br>i + j &lt; n</p>
<p>返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。</p>
<p>提示:</p>
<p>1 &lt;= nums.length &lt;= 104<br>0 &lt;= nums[i] &lt;= 1000</p>
<p>示例1:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>
<p>示例2:</p>
<pre class="line-numbers language-shell"><code class="language-shell">输入: nums = [2,3,0,1,4]
输出: 2<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
</blockquote>
<h4 id="解题思路-7"><a href="#解题思路-7" class="headerlink" title="解题思路"></a>解题思路</h4><blockquote>
<p>局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。</p>
<p>解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！</p>
<p>这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。</p>
<p>​<img src="https://resource.weizhanjun.com/public/images/20230112145739.png" alt="">​</p>
<p>图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）</p>
</blockquote>
<h4 id="Go-题解-5"><a href="#Go-题解-5" class="headerlink" title="Go 题解"></a>Go 题解</h4><pre class="line-numbers language-go"><code class="language-go"><span class="token keyword">func</span> <span class="token function">jump</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token number">0</span>
    <span class="token punctuation">}</span>
    result <span class="token operator">:=</span> <span class="token number">0</span> <span class="token comment" spellcheck="true">// 记录走的最大步数</span>
    curDistance <span class="token operator">:=</span> <span class="token number">0</span> <span class="token comment" spellcheck="true">// 当前覆盖最远距离下标</span>
    nextDistance <span class="token operator">:=</span> <span class="token number">0</span> <span class="token comment" spellcheck="true">// 下一步覆盖最远距离下标</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token comment" spellcheck="true">// 更新下一步覆盖最远距离下标</span>
        nextDistance <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span>i<span class="token punctuation">,</span> nextDistance<span class="token punctuation">)</span>
        <span class="token comment" spellcheck="true">// 遇到当前覆盖最远距离下标</span>
        <span class="token keyword">if</span> i <span class="token operator">==</span> curDistance <span class="token punctuation">{</span>
            <span class="token comment" spellcheck="true">// 如果当前覆盖最远距离下标不是终点</span>
            <span class="token keyword">if</span> curDistance <span class="token operator">!=</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">{</span>
                <span class="token comment" spellcheck="true">// 跳下一步</span>
                result<span class="token operator">++</span>
                <span class="token comment" spellcheck="true">// 更新当前覆盖最远距离下标</span>
                curDistance <span class="token operator">=</span> nextDistance
                <span class="token comment" spellcheck="true">// 下一步的覆盖范围已经可以达到终点，结束循环</span>
                <span class="token keyword">if</span> nextDistance <span class="token operator">>=</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">{</span>
                    <span class="token keyword">break</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">break</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">max</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> y <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> x <span class="token operator">-</span> y <span class="token operator">></span> <span class="token number">0</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> x
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> y
<span class="token punctuation">}</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="C-题解-6"><a href="#C-题解-6" class="headerlink" title="C++ 题解"></a>C++ 题解</h4><pre class="line-numbers language-c"><code class="language-c">class Solution <span class="token punctuation">{</span>
public<span class="token punctuation">:</span>
    <span class="token keyword">int</span> <span class="token function">jump</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> curDistance <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> nextDistance <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>

        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            nextDistance <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>i<span class="token operator">+</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> nextDistance<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">==</span> curDistance<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator">!=</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    result<span class="token operator">++</span><span class="token punctuation">;</span>
                    curDistance <span class="token operator">=</span> nextDistance<span class="token punctuation">;</span>
                    <span class="token keyword">if</span> <span class="token punctuation">(</span>nextDistance <span class="token operator">>=</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                        <span class="token keyword">break</span><span class="token punctuation">;</span>
                    <span class="token punctuation">}</span>
                <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                    <span class="token keyword">break</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="Python-题解-5"><a href="#Python-题解-5" class="headerlink" title="Python 题解"></a>Python 题解</h4><pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Solution</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">jump</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> nums<span class="token punctuation">:</span> List<span class="token punctuation">[</span>int<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> int<span class="token punctuation">:</span>
        <span class="token keyword">if</span> len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token number">0</span>
        result <span class="token operator">=</span> <span class="token number">0</span>
        curDistance <span class="token operator">=</span> <span class="token number">0</span>
        nextDistance <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span>len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            nextDistance <span class="token operator">=</span> max<span class="token punctuation">(</span>i<span class="token operator">+</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> nextDistance<span class="token punctuation">)</span>
            <span class="token keyword">if</span> i<span class="token operator">==</span>curDistance<span class="token punctuation">:</span>
                <span class="token keyword">if</span> i <span class="token operator">!=</span> len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">:</span>
                    result<span class="token operator">+</span><span class="token operator">+</span>
                    curDistance <span class="token operator">=</span> nextDistance
                    <span class="token keyword">if</span> nextDistance <span class="token operator">>=</span>len<span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">:</span>
                        <span class="token keyword">break</span>
                <span class="token keyword">else</span><span class="token punctuation">:</span>
                    <span class="token keyword">break</span>
        <span class="token keyword">return</span> result<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h4 id="算法优化总结-4"><a href="#算法优化总结-4" class="headerlink" title="算法优化总结"></a>算法优化总结</h4><blockquote>
<p>理解本题的关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最小步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。</p>
</blockquote>
<p>‍</p>
<p>‍</p>
<p>‍</p>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        文章作者:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="../../../../../../about" rel="external nofollow noreferrer">卫占军</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        文章链接:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="https://blog.weizhanjun.com">https://blog.weizhanjun.com</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        版权声明:
                    </i>
                </span>
                <span class="reprint-info">
                    本博客所有文章除特別声明外，均采用
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    许可协议。转载请注明来源
                    <a href="../../../../../../about" target="_blank">卫占军</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="../../../../../../tags/LeetCode/">
                                    <span class="chip bg-color">LeetCode</span>
                                </a>
                            
                                <a href="../../../../../../tags/贪心算法/">
                                    <span class="chip bg-color">贪心算法</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="../../../../../../libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="../../../../../../libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
        </div>
    </div>

    

    

    

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="far fa-dot-circle"></i>&nbsp;本篇
            </div>
            <div class="card">
                <a href="">
                    <div class="card-image">
                        
                        
                        <img src="https://resource.weizhanjun.com/public/medias/featureimages/6.jpg" class="responsive-img" alt="贪心算法">
                        
                        <span class="card-title">贪心算法</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2023-01-20
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-user fa-fw"></i>
                            卫占军
                            
                        </span>
                    </div>
                </div>

                
                <div class="card-action article-tags">
                    
                    <a href="../../../../../../tags/LeetCode/">
                        <span class="chip bg-color">LeetCode</span>
                    </a>
                    
                    <a href="../../../../../../tags/贪心算法/">
                        <span class="chip bg-color">贪心算法</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="../kubernetes-2jjikh.html/">
                    <div class="card-image">
                        
                        
                        <img src="https://resource.weizhanjun.com/public/medias/featureimages/13.jpg" class="responsive-img" alt="初识Kubernetes">
                        
                        <span class="card-title">初识Kubernetes</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2023-01-20
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="../../../../../../categories/posts/" class="post-category">
                                    _posts
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="../../../../../../tags/kubernetes/">
                        <span class="chip bg-color">kubernetes</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>


<script>
    $('#articleContent').on('copy', function (e) {
        // IE8 or earlier browser is 'undefined'
        if (typeof window.getSelection === 'undefined') return;

        var selection = window.getSelection();
        // if the selection is short let's not annoy our users.
        if (('' + selection).length < Number.parseInt('60')) {
            return;
        }

        // create a div outside of the visible area and fill it with the selected text.
        var bodyElement = document.getElementsByTagName('body')[0];
        var newdiv = document.createElement('div');
        newdiv.style.position = 'absolute';
        newdiv.style.left = '-99999px';
        bodyElement.appendChild(newdiv);
        newdiv.appendChild(selection.getRangeAt(0).cloneContents());

        // we need a <pre> tag workaround.
        // otherwise the text inside "pre" loses all the line breaks!
        if (selection.getRangeAt(0).commonAncestorContainer.nodeName === 'PRE' || selection.getRangeAt(0).commonAncestorContainer.nodeName === 'CODE') {
            newdiv.innerHTML = "<pre>" + newdiv.innerHTML + "</pre>";
        }

        var url = document.location.href;
        newdiv.innerHTML += '<br />'
            + '来源: 个人博客<br />'
            + '文章作者: 卫占军<br />'
            + '文章链接: <a href="' + url + '">' + url + '</a><br />'
            + '本文章著作权归作者所有，任何形式的转载都请注明出处。';

        selection.selectAllChildren(newdiv);
        window.setTimeout(function () {bodyElement.removeChild(newdiv);}, 200);
    });
</script>


<!-- 代码块功能依赖 -->
<script type="text/javascript" src="../../../../../../libs/codeBlock/codeBlockFuction.js"></script>



<!-- 代码语言 -->

<script type="text/javascript" src="../../../../../../libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="../../../../../../libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="../../../../../../libs/codeBlock/codeShrink.js"></script>



    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="../../../../../../libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('0'),
            headingSelector: 'h2, h3, h4'
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>




    <footer class="page-footer bg-color">
    
        <link rel="stylesheet" href="../../../../../../libs/aplayer/APlayer.min.css">
<style>
    .aplayer .aplayer-lrc p {
        
        display: none;
        
        font-size: 12px;
        font-weight: 700;
        line-height: 16px !important;
    }

    .aplayer .aplayer-lrc p.aplayer-lrc-current {
        
        display: none;
        
        font-size: 15px;
        color: #542674;
    }

    
    .aplayer.aplayer-fixed.aplayer-narrow .aplayer-body {
        left: -66px !important;
    }

    .aplayer.aplayer-fixed.aplayer-narrow .aplayer-body:hover {
        left: 0px !important;
    }

    
</style>
<div class="">
    
    <div class="row">
        <meting-js class="col l8 offset-l2 m10 offset-m1 s12"
                   server="netease"
                   type="playlist"
                   id="531576456"
                   fixed='true'
                   autoplay='false'
                   theme='#542674'
                   loop='all'
                   order='random'
                   preload='auto'
                   volume='0.7'
                   list-folded='true'
        >
        </meting-js>
    </div>
</div>

<script src="../../../../../../libs/aplayer/APlayer.min.js"></script>
<script src="../../../../../../libs/aplayer/Meting.min.js"></script>

    

    <div class="container row center-align"
         style="margin-bottom: 0px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2019-2023</span>
            
            <a href="../../../../../../about" target="_blank">卫占军</a>
            |&nbsp;Powered by&nbsp;<a href="https://hexo.io/" target="_blank">Hexo</a>
            |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a>
            
            <br>
            
            
            
                
            
            
                <span id="busuanzi_container_site_pv">
                &nbsp;|&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;
                    <span id="busuanzi_value_site_pv" class="white-color"></span>
            </span>
            
            
                <span id="busuanzi_container_site_uv">
                &nbsp;|&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;
                    <span id="busuanzi_value_site_uv" class="white-color"></span>
            </span>
            
            <br>

            <!-- 运行天数提醒. -->
            
            <br>
            
                <span id="icp"><img src="../../../../../../medias/icp.png"
                                    style="vertical-align: text-bottom;"/>
                <a href="https://beian.miit.gov.cn/" target="_blank">京ICP备2023001141号</a>
            </span>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/weizj2000" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:weizj2000@gmail.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>







    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=1084081287" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 1084081287" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







</div>
    </div>
</footer>

<div class="progress-bar"></div>


    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('../../../../../../search.xml', 'searchInput', 'searchResult');
});
</script>

    <!-- 白天和黑夜主题 -->
<div class="stars-con">
    <div id="stars"></div>
    <div id="stars2"></div>
    <div id="stars3"></div>  
</div>

<script>
    function switchNightMode() {
        $('<div class="Cuteen_DarkSky"><div class="Cuteen_DarkPlanet"></div></div>').appendTo($('body')),
        setTimeout(function () {
            $('body').hasClass('DarkMode') 
            ? ($('body').removeClass('DarkMode'), localStorage.setItem('isDark', '0'), $('#sum-moon-icon').removeClass("fa-sun").addClass('fa-moon')) 
            : ($('body').addClass('DarkMode'), localStorage.setItem('isDark', '1'), $('#sum-moon-icon').addClass("fa-sun").removeClass('fa-moon')),
            
            setTimeout(function () {
            $('.Cuteen_DarkSky').fadeOut(1e3, function () {
                $(this).remove()
            })
            }, 2e3)
        })
    }
</script>

    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>


    <script src="../../../../../../libs/materialize/materialize.min.js"></script>
    <script src="../../../../../../libs/masonry/masonry.pkgd.min.js"></script>
    <script src="../../../../../../libs/aos/aos.js"></script>
    <script src="../../../../../../libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="../../../../../../libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="../../../../../../js/matery.js"></script>

    

    
    
    
        
        <script type="text/javascript">
            // 只在桌面版网页启用特效
            var windowWidth = $(window).width();
            if (windowWidth > 768) {
                document.write('<script type="text/javascript" src="../../../../../../libs/others/sakura.js"><\/script>');
            }
        </script>
    

    <!-- 雪花特效 -->
     
        <script type="text/javascript">
            // 只在桌面版网页启用特效
            var windowWidth = $(window).width();
            if (windowWidth > 768) {
                document.write('<script type="text/javascript" src="../../../../../../libs/others/snow.js"><\/script>');
            }
        </script>
    

    <!-- 鼠标星星特效 -->
     
        <script type="text/javascript">
            // 只在桌面版网页启用特效
            var windowWidth = $(window).width();
            if (windowWidth > 768) {
                document.write('<script type="text/javascript" src="../../../../../../libs/others/star.js"><\/script>');
            }
        </script>
    

    

    <!-- Baidu Analytics -->

    <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

    
    <script src="../../../../../../libs/others/clicklove.js" async="async"></script>
    
    
    <script async src="../../../../../../libs/others/busuanzi.pure.mini.js"></script>
    

    

    

    <!--腾讯兔小巢-->
    
    
    <script type="text/javascript" color="0,0,255"
        pointColor="0,0,255" opacity='0.7'
        zIndex="-1" count="99"
        src="../../../../../../libs/background/canvas-nest.js"></script>
    

    
    
    <script type="text/javascript" size="150" alpha='0.6'
        zIndex="-1" src="../../../../../../libs/background/ribbon-refresh.min.js" async="async"></script>
    

    
    <script type="text/javascript" src="../../../../../../libs/background/ribbon-dynamic.js" async="async"></script>
    

    
    <script src="../../../../../../libs/instantpage/instantpage.js" type="module"></script>
    

</body>

</html>
